#
# @lc app=leetcode.cn id=55 lang=python3
#
# [55] 跳跃游戏
#

# @lc code=start
from typing import List

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        length = len(nums)
        if length <= 1:
            return True
        
        nextPosition = 0
        currentIndex = 0
        nextRightBounds = 0
       
        while currentIndex < len(nums):
            while currentIndex <= nextPosition:
                rb = self.rightBounds(nums, currentIndex)
                if rb >= length - 1:
                    return True
                elif rb > nextRightBounds:
                    nextRightBounds = rb
                    
                currentIndex += 1
            
            # 说明跳不过去        
            if nextRightBounds == nextPosition:
                return False
            elif nextRightBounds >= len(nums) - 1:
                return True
            else:
                currentIndex = nextPosition + 1
                nextPosition = nextRightBounds
                
        
        return False
    
    # 当前位置可以向右跳的位置
    def rightBounds(self, nums: List[int], index: int) -> int:
        assert index >= 0 and index < len(nums)
        # 超过了最后一个位置，就返回超过的位置
        if index + nums[index] >= len(nums) - 1:
            return index + nums[index]
        
        steps = nums[index]
        while nums[index + steps] == 0 and steps > 0:
            steps -= 1
        return index + steps
            
            
Solution().canJump([0]) 
        
# @lc code=end

